#ifndef DICTIONARY_H_INCLUDED
#define DICTIONARY_H_INCLUDED

#include "Vector.h"
#include "IteratorForward.h"

namespace CEngine {

template<class Element, class Key = U64>
class Dictionary {
        struct DictionaryIterator;
        struct Node;

    public:

        ///Creates an empty tree, relativeKey is false.
        Dictionary(void);

        ///Creates a dictionary with element as the root, and relativeKey is set to true.
        ///key must be a member of element.
        Dictionary(const Element& element, const Key& key);

        ///Creates a copy of dict.
        Dictionary(const Dictionary& dict);

        ///Creates a dictionary with the elements of vector.
        ///key must be a member of the first element in vector.
        Dictionary(const Vector<Element>& vector, const Key& key);

        ///Creates a dictionary with the elements between first and last (including first, but not last).
        ///key must be a member of first.
        template<class T>
        Dictionary(const Iterator<T>& first, const Iterator<T>& last, const Key& key);

        ///Copies dict (including relativeKey).
        ///Destroys previous elements.
        Dictionary&
        operator= (const Dictionary& dict);

        ///Copies the contents of vector (relativeKey must be true).
        ///Destroys previous elements.
        Dictionary&
        operator= (const Vector<Element>& vector);

        ///Destructor.
        ~Dictionary(void);

        ///Iterator function. Returns an iterator to the first element in the dictionary.
        DictionaryIterator
        begin(void) const;

        ///Iterator function. Returns an iterator to the last element in the dictionary.
        DictionaryIterator
        rBegin(void) const;

        ///Iterator function. Returns an iterator to an element outside of the dictionary.
        ///Do not dereference.
        DictionaryIterator
        end(void) const;

        ///Access function. Returns the element with the lowest key.
        Element&
        min(void) const;

        ///Access function. Returns the element with the highest key.
        Element&
        max(void) const;

        ///Inserts element into the dictionary using a relative key.
        ///Returns an iterator to the element. If the key already exists element won't be added,
        ///and an iterator will be returned to the stored element.
        ///relativeKey MUST be true.
        DictionaryIterator
        insert(const Element& element);

        ///Inserts element into the dictionary using key.
        ///Returns an iterator to the element. If the key already exists element won't be added,
        ///and an iterator will be returned to the stored element.
        ///relativeKey MUST be false.
        DictionaryIterator
        insert(const Element& element, const Key& key);

        ///Removes the element associated with key from the dictionary.
        void
        erase(const Key& key);

        ///Empties the dictionary.
        void
        clear(void);

        ///Returns if the dictionary is empty or not.
        bool
        isEmpty(void) const;

        ///Returns the size of the dictionary.
        U64
        getSize(void) const;

        void
        printTree(void) const;

    private:

        Vector<Node> array;
        Node* root;

        //Node* min;
        //Node* max;

        U64 keyOffset;
        bool relativeKey;

        const static Node* const nil;

        Node* skew(Node* root);
        Node* split(Node* root);
        Node* search(Key key);
        DictionaryIterator createIterator(const Node* node) const;
        static Node* createNil(void);

        friend class Iterator<Element>;

        ///Iterator initializer used by the generic Iterator class.
        struct DictionaryIterator {
            Dictionary<Element, Key>* basePointer;
            Node* currentPointer;
        };

        ///Internal node structure that the dictionary is made of.
        struct Node {
            Node* parent;
            Node* left;
            Node* right;

            Element element;
            Key key;

            U8 level;

            Node(void);
            Node(const Node* left, const Node* right);
        };
};

}

#include "DictionaryCore.h"

#endif // DICTIONARY_H_INCLUDED
